package Enviroment;

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.*;

import Logic.Game;

public class Node<E extends QuadItem>
{
	private static final int MAX_ENTITIES = 4; //max number a node can hold before it splits
	private static final int MAX_DEPTH = 2;
	//Items within this node
	protected ArrayList<E> containedItems;
	//items that can not be pushed further down
	protected ArrayList<E> stuckItems;
	//Nodes parent node
	protected final Node<E> PARENT;
	
	protected Node<E> NE = null;
	protected Node<E> SE = null;
	protected Node<E> SW = null;
	protected Node<E> NW = null;

	protected final double x; //x position in environment
	protected final double y; //y position in environment
	protected final double width; //width of the node

	public Node(double x, double y, double width, Node<E> parent)
	{
		this.x = x;
		this.y = y;
		this.width = width;
		this.PARENT = parent;
		this.containedItems = new ArrayList<E>();
		this.stuckItems = new ArrayList<E>();
	}
	
	public void insert(E item)
	{
		if(NE == null) //if NE is null then they are all null
		{
			this.containedItems.add(item);
			if(this.containedItems.size() > MAX_ENTITIES && this.width > Game.ENVIROMENT_WIDTH/(Math.pow(2, MAX_DEPTH)))
				split();
		}
		else
			insertToLeaf(item);
	}
	
	public void split()
	{
		double newWidth = this.width/2;
		
		double x_ne = this.x + newWidth/2;
		double y_ne = this.y - newWidth/2;
		this.NE = new Node<E>(x_ne, y_ne, newWidth, this);
		
//		System.out.println("NE: "+x_ne +" "+ y_ne + " " + newWidth);
		
		double x_se = this.x + newWidth/2;
		double y_se = this.y + newWidth/2;
		this.SE = new Node<E>(x_se, y_se, newWidth, this);
		
//		System.out.println("SE: "+x_se +" "+ y_se + " " + newWidth);
		
		double x_sw = this.x - newWidth/2;
		double y_sw = this.y + newWidth/2;
		this.SW = new Node<E>(x_sw, y_sw, newWidth, this);
		
//		System.out.println("SW: "+x_sw +" "+ y_sw + " " + newWidth);
		
		double x_nw = this.x - newWidth/2;
		double y_nw = this.y - newWidth/2;
		this.NW = new Node<E>(x_nw, y_nw, newWidth, this);
		
//		System.out.println("NW: "+x_nw +" "+ y_nw + " " + newWidth);
		
//		System.out.println("\n\n");
		
		for(E item : containedItems)
			insertToLeaf(item);
		this.containedItems = new ArrayList<E>(1);
	}
	
	private void insertToLeaf(E item)
	{
		Bounds bound = item.getBounds();
		if(withinNode(NE, bound))
			NE.insert(item);
		else if(withinNode(SE, bound))
			SE.insert(item);
		else if(withinNode(SW, bound))
			SW.insert(item);
		else if(withinNode(NW, bound))
			NW.insert(item);
		else
			this.stuckItems.add(item);
	}
		
	private boolean withinNode(Node<E> node, Bounds bound)
	{
		return node.within(bound);
	}
	
	private boolean within(Bounds bound)
	{
		return isItemInNode(this, bound);
	}
	
	private boolean withinNode(Node<E> node, int x, int y)
	{
		return node.within(x, y);
	}
	
	private boolean within(int x, int y)
	{
		return isPointInNode(this, x, y);
	}
	
	public static boolean isPointInNode(Node node, int x, int y)
	{
		double node_X = node.x - node.width/2;
		double node_Y = node.y - node.width/2;
		Rectangle2D s = new Rectangle2D.Double(node_X, node_Y, node.width, node.width);
		return s.contains(new Point2D.Double(x, y));
	}
	
	public static boolean isItemInNode(Node node, Bounds bound) {
		double bound_X = bound.X - bound.WIDTH/2;
		double bound_Y = bound.Y - bound.HEIGHT/2;
		
		double node_X = node.x - node.width/2;
		double node_Y = node.y - node.width/2;
		return isItemInNode(node_X, node_Y, node.width, bound_X, bound_Y, bound.WIDTH, bound.HEIGHT);
	}
	
	public static boolean isItemInNode(double sx, double sy, double sw, double rx, double ry, double rw, double rh) {
	    Rectangle2D s = new Rectangle2D.Double(sx, sy, sw, sw),
	                r = new Rectangle2D.Double(rx, ry, rw, rh);
	    return s.contains(r);
	}
	
	public static boolean doesItemIntersectNode(Node node, Bounds bound){
		double bound_X = bound.X - bound.WIDTH/2;
		double bound_Y = bound.Y - bound.HEIGHT/2;
		
		double node_X = node.x - node.width/2;
		double node_Y = node.y - node.width/2;
		return doesItemIntersectNode(node_X, node_Y, node.width, bound_X, bound_Y, bound.WIDTH, bound.HEIGHT);
	}
	
	public static boolean doesItemIntersectNode(double sx, double sy, double sw, double rx, double ry, double rw, double rh) {
	    Rectangle2D s = new Rectangle2D.Double(sx, sy, sw, sw),
	                r = new Rectangle2D.Double(rx, ry, rw, rh);
	    return s.intersects(r);
	}
	
	public void removeItem(E item)
	{
		if(this.stuckItems.contains(item))
			this.stuckItems.remove(item);
		else if(NE != null)
			this.removeFromLeaf(item);
		else if(this.containedItems.contains(item))
			this.containedItems.remove(item);
	}
	
	private void removeFromLeaf(E item)
	{
		Bounds bound = item.getBounds();
		if(withinNode(NE, bound))
			NE.removeItem(item);
		else if(withinNode(SE, bound))
			SE.removeItem(item);
		else if(withinNode(SW, bound))
			SW.removeItem(item);
		else if(withinNode(NW, bound))
			NW.removeItem(item);
	}
	
	private Node<E> ROOT()
	{
		Node<E> node = this;
		while(node.PARENT != null)
			node = node.PARENT;
		return node;
	}
	
	public String toString()
	{
		String s = "\n*********************\n"; 
		s += x+" "+y+" "+width+"\nStuck:";
		for(E node : this.stuckItems)
			s += "\n"+node.toString();
		
		s += "\nContained items:\n";
		for(E node : this.containedItems)
			s += "\n"+node.toString();
		
		s += "\nChildren:\n";
		
		if(NE != null)
		{
			s += "NE: "+NE.toString() +"\n";
			s += "SE: "+SE.toString() +"\n";
			s += "SW: "+SW.toString() +"\n";
			s += "NW: "+NW.toString() +"\n";
		}
		
		s += "\n*********************\n";
		
		return s;
	}
	
	public void render(Graphics2D g2d)	{
		double xt = this.x - this.width/2;
		double yt = this.y - this.width/2;
		g2d.drawRect((int)xt, (int)yt, (int)this.width, (int)this.width);
		
		g2d.setColor(Color.RED);
		for(E item : containedItems)
			item.render(g2d);
		for(E item : stuckItems)
			item.render(g2d);
		g2d.setColor(Color.WHITE);
		
		if(NE != null)
		{
//			g2d.setColor(Color.PINK);
			NW.render(g2d);
//			g2d.setColor(Color.GREEN);
			NE.render(g2d);
//			g2d.setColor(Color.BLUE);
			SE.render(g2d);
//			g2d.setColor(Color.YELLOW);
			SW.render(g2d);
		}
	}
	
	//only called on the root node
	public List<E> tick()
	{
//		tickNodes();
		
		final List<E> moved = Collections.synchronizedList(new ArrayList<E>(stuckItems.size() + containedItems.size()));

//		for(E obj : stuckItems)
//			obj.tick();
		
		for(int i = 0; i < stuckItems.size(); i++)
		{
			E item = stuckItems.get(i);
			item.tick();
			moved.add(item);
			stuckItems.remove(item);
			i--;
		}
		
//		for(E obj : containedItems)
//			obj.tick();
		
		for(int i = 0; i < containedItems.size(); i++)
		{
			E item = containedItems.get(i);
			item.tick();
			if(!within(item.getBounds()))
			{
				moved.add(item);
				containedItems.remove(item);
				i--;
			}
		}
		
		if(NE != null)
		{
			ArrayList<Thread> threads = new ArrayList<Thread>(4);
			Thread thread = new Thread(new Runnable() 
			{
				@Override
			    public void run() 
			    {
					moved.addAll(NE.tickNodes());
			    }
			});
			threads.add(thread);
			thread.start();
			
			thread = new Thread(new Runnable() 
			{
				@Override
			    public void run() 
			    {
					moved.addAll(SE.tickNodes());
			    }
			});
			threads.add(thread);
			thread.start();
			
			thread = new Thread(new Runnable() 
			{
				@Override
			    public void run() 
			    {
					moved.addAll(SW.tickNodes());
			    }
			});
			threads.add(thread);
			thread.start();
			
			thread = new Thread(new Runnable() 
			{
				@Override
			    public void run() 
			    {
					moved.addAll(NW.tickNodes());
			    }
			});
			threads.add(thread);
			thread.start();
			
			for(Thread t : threads)
				try 
				{
					t.join();
				} catch (InterruptedException e) 
				{
					System.out.println(e.getMessage());
					e.printStackTrace();
				}
		}
		
//		Node<E> ROOT = ROOT();
//		for(E item : moved)
//			insert(item);
		return moved;
	}
	
	private ArrayList<E> tickNodes()
	{
		ArrayList<E> moved = new ArrayList<E>(stuckItems.size() + containedItems.size());
		
//		for(E obj : stuckItems)
//			obj.tick();
		for(int i = 0; i < stuckItems.size(); i++)
		{
			E item = stuckItems.get(i);
			item.tick();
			moved.add(item);
			stuckItems.remove(item);
			i--;
		
		}
//		for(E obj : containedItems)
//			obj.tick();
	
		
		for(int i = 0; i < containedItems.size(); i++)
		{
			E item = containedItems.get(i);
			item.tick();
			if(!within(item.getBounds()))
			{
				moved.add(item);
				containedItems.remove(item);
				i--;
			}
		}
		
		if(NE != null)
		{
			moved.addAll(NE.tickNodes());
			moved.addAll(SE.tickNodes());
			moved.addAll(SW.tickNodes());
			moved.addAll(NW.tickNodes());
		}
		
		return moved;
	}
	
//	private void reshuffle()
//	{
//		ArrayList<E> stuck = new ArrayList<E>(this.stuckItems);
//		this.stuckItems = new ArrayList<E>(this.stuckItems.size()+10);
//		
//		for(E obj : stuck)
//			ROOT().insert(obj);
//		
//		for(int i = 0; i < containedItems.size(); i++)
//		{
//			E obj = containedItems.get(i);
//			if(!within(obj.getBounds()))
//			{
//				containedItems.remove(i--);
//				ROOT().insert(obj);
//			}
//		}
//		
//		if(NE != null)
//		{
//			NE.reshuffle();
//			SE.reshuffle();
//			SW.reshuffle();
//			NW.reshuffle();
//		}
//	}
	
	public void checkCollisions()
	{
//		checkCollisions(new ArrayList<E>(1));
		for(int i = 0; i < stuckItems.size(); i++)
			for(int j = 0; j < stuckItems.size(); j++)
				if(i != j)
					stuckItems.get(i).hasCollided(stuckItems.get(j));
		
		for(int i = 0; i < containedItems.size(); i++)
			for(int j = 0; j < containedItems.size(); j++)
				if(i != j)
				 	containedItems.get(i).hasCollided(containedItems.get(j));
		
		if(NE != null)
		{
			ArrayList<Thread> threads = new ArrayList<Thread>(4);
			Thread thread = new Thread(new Runnable() 
			{
				@Override
			    public void run() 
			    {
					NE.checkCollisions(stuckItems);
			    }
			});
			threads.add(thread);
			thread.start();
			
			thread = new Thread(new Runnable() 
			{
				@Override
			    public void run() 
			    {
					SE.checkCollisions(stuckItems);
			    }
			});
			threads.add(thread);
			thread.start();
			
			thread = new Thread(new Runnable() 
			{
				@Override
			    public void run() 
			    {
					SW.checkCollisions(stuckItems);
			    }
			});
			threads.add(thread);
			thread.start();
			
			thread = new Thread(new Runnable() 
			{
				@Override
			    public void run() 
			    {
					NW.checkCollisions(stuckItems);
			    }
			});
			threads.add(thread);
			thread.start();
			
			for(Thread t : threads)
				try 
				{
					t.join();
				} catch (InterruptedException e) 
				{
					System.out.println(e.getMessage());
					e.printStackTrace();
				}
		}
	}
	
	private void checkCollisions(ArrayList<E> items)
	{
		for(int i = 0; i < stuckItems.size(); i++)
			for(int j = 0; j < stuckItems.size(); j++)
				if(i != j)
					stuckItems.get(i).hasCollided(stuckItems.get(j));
		
		for(int i = 0; i < containedItems.size(); i++)
		{
			for(int j = 0; j < containedItems.size(); j++)
			{
				if(i != j)
				 	containedItems.get(i).hasCollided(containedItems.get(j));
			}
			for(int k = 0; k < items.size(); k++)
					containedItems.get(i).hasCollided(items.get(k));
			for(int k = 0; k < stuckItems.size(); k++)
				containedItems.get(i).hasCollided(stuckItems.get(k));
			
		}
		
		final ArrayList<E> itemsDown = new ArrayList<E>(items.size() + stuckItems.size());
		itemsDown.addAll(stuckItems);
		itemsDown.addAll(items);
		if(NE != null)
		{
//			NE.checkCollisions(getIntersects(NE, itemsDown));
//			SE.checkCollisions(getIntersects(SE, itemsDown));
//			SW.checkCollisions(getIntersects(SW, itemsDown));
//			NW.checkCollisions(getIntersects(NW, itemsDown));
			NE.checkCollisions(itemsDown);
			SE.checkCollisions(itemsDown);
			SW.checkCollisions(itemsDown);
			NW.checkCollisions(itemsDown);
			
		}
	}
	
	private ArrayList<E> getIntersects(Node<E> node, ArrayList<E> items)
	{
		ArrayList<E> intersectingItems = new ArrayList<E>(items.size());
		for(E item : items)
			if(doesItemIntersectNode(node, item.getBounds()))
				intersectingItems.add(item);
		return items;
	}
	
	public ArrayList<E> retrieveItems(int x, int y)
	{
		return retrieve(x, y);
	}
	
	private ArrayList<E> retrieve(int x, int y)
	{
		ArrayList<E> items = new ArrayList<E>();
		
		if(within(x, y))
		{
			items.addAll(stuckItems);
			for(E item : stuckItems)
				if(item instanceof RectangleItem)
					((RectangleItem)item).changeColorStuck();
			
			items.addAll(containedItems);
			for(E item : containedItems)
				if(item instanceof RectangleItem)
					((RectangleItem)item).changeColor();
		}
		
		if(NE != null)
		{
			if(withinNode(NE, x, y))
			{
//				System.out.println("NE");
				items.addAll(NE.retrieve(x, y));
			}
			else if(withinNode(SE, x, y))
			{
//				System.out.println("SE");
				items.addAll(SE.retrieve(x, y));				
			}
			else if(withinNode(SW, x, y))
			{
//				System.out.println("SW");
				items.addAll(SW.retrieve(x, y));
			}
			else if(withinNode(NW, x, y))
			{
//				System.out.println("NW");
				items.addAll(NW.retrieve(x, y));
			}
		}
		
		return items;
	}
	
	private ArrayList<E> retrieveItemsInBound(Bounds bound)
	{
		ArrayList<E> items = new ArrayList<E>();
		
		return items;
	}
}

